package gold.digger;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Created by fanzhenyu02 on 2020/2/24.
 */
public class LC39 {


    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        return new ArrayList<>(combinationSumRecur(candidates, target));
    }

    public Set<List<Integer>> combinationSumRecur(int[] candidates, int target) {
        Set<List<Integer>> result = new HashSet<>();

        if (target <= 0 || null == candidates || candidates.length <= 0) {
            return result;
        }

        for (int i = 0; i < candidates.length; i++) {
            if (candidates[i] == target) {
                List<Integer> curCombList = new ArrayList<>();
                curCombList.add(candidates[i]);
                result.add(curCombList);
                continue;
            }

            if (candidates[i] > target) {
                continue;
            }

            Set<List<Integer>> subResult = combinationSumRecur(candidates, target - candidates[i]);
            for (List<Integer> curCombination : subResult) {
                curCombination.add(candidates[i]);
                curCombination.sort(new Comparator<Integer>() {
                    @Override
                    public int compare(Integer o1, Integer o2) {
                        return o1 - o2;
                    }
                });
            }
            result.addAll(subResult);
        }

        return result;
    }

    public static void main(String[] args) {
        LC39 an = new LC39();
        int[] arr = {8,7,4,3};
        int target = 11;

        System.out.println(an.combinationSumRecur(arr, target));
    }

}
